
//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * 第一遍 2/28
     * @param head
     * @param left
     * @param right
     * @return
     */
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        if (left == 1) return reverseN(head, right);
//
//        head.next = reverseBetween(head.next, left - 1, right - 1);
//        return head;
//    }
//
//    // 后驱节点
//    ListNode pre = null;
//    ListNode reverseN(ListNode head, int n) {
//        if (n == 1) {
//            // 记录第n+1个节点
//            pre = head.next;
//            return head;
//        }
//        // 以head.next为起点，需要反转前n-1个节点
//        ListNode last = reverseN(head.next, n - 1);
//        head.next.next = head;
//        // 让反转之后的head节点和后面的节点连接起来
//        head.next = pre;
//        return last;
//    }


    /**
     * 第二遍 3/3
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        if (left == 1) return reverseN(head, right);
//
//        head.next = reverseBetween(head.next, left - 1, right - 1);
//        return head;
//    }
//
//    // 后驱节点
//    ListNode pre = null;
//    ListNode reverseN(ListNode head, int n) {
//        if (n == 1) {
//            // 记录第n+1个节点
//            pre = head.next;
//            return head;
//        }
//
//        // 以head.next为起点，需要反转n-1个节点
//        ListNode last = reverseN(head.next, n - 1);
//        // 1 <- 4
//        head.next.next = head;
//        // null <- 1 <- 4
//        head.next = pre;
//        return last;
//    }


    /**
     * 第三遍 3/7
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 判断head链表
        if (left == 1) return reverseN(left, right);


    }
}
//leetcode submit region end(Prohibit modification and deletion)
